package quasilinqueue;

import harness.Queue;
import harness.Random;
import java.util.Collection;
import java.util.Iterator;
import java.util.concurrent.atomic.AtomicReference;

public class LockFreeQueue<T> implements Queue {

    public Object poll(int threadId, Random rng) {
        return deq();
    }

    public boolean offer(Object e, int threadId, Random rng) {
        enq((T) e);
        return true;
    }

        private static class Node<T>{
                public final T value;
                public final AtomicReference<Node<T>> next;     
                public Node(T value){
                        this.value = value;
                        next = new AtomicReference<Node<T>>(null);
                }
        }
        
        private final AtomicReference<Node<T>> head;
        private final AtomicReference<Node<T>> tail;
        
        public LockFreeQueue() {
                Node<T> sentinal = new Node<T>(null);
                head = new AtomicReference<Node<T>>(sentinal);
                tail = new AtomicReference<Node<T>>(sentinal);
        }
        
        public T deq(){
                while(true){
                        Node<T> first = head.get();
                        Node<T> last = tail.get();
                        Node<T> next = first.next.get();
                        if (first == head.get()){
                                if (first == last){
                                        if (next == null){
                                                return null;
                                        }
                                        tail.compareAndSet(last, next);
                                } else {
                                        T value = next.value;
                                        if (head.compareAndSet(first, next))
                                                return value;
                                }
                        }
                }
        }

        public void enq(T value) {
                Node<T> newNode = new Node<T>(value);
                while(true){
                        Node<T> lastNode = tail.get();
                        Node<T> nextNode = lastNode.next.get();
                        //If equals, we have a legit snapshot
                        if (lastNode == tail.get()){
                                //Check if next after last do not exist
                                if (nextNode == null){
                                        //Attempt atomic switch
                                        if (lastNode.next.compareAndSet(nextNode, newNode)){
                                                tail.compareAndSet(lastNode, newNode);
                                                return;
                                        }
                                } else {
                                        //Concurrent enq, help him complete
                                        tail.compareAndSet(lastNode, nextNode);
                                }
                        }
                }
        }
        
        public void enq(T value, long seed) 
        {
                enq(value);
        };

        public T deq(long seed){
                return deq();
        }

}
